// Created by WXX on 2021/11/30 14:48
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：7.6 MB, 在所有 C++ 提交中击败了91.54%的用户
 */
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [&](vector<int> &a, vector<int> &b) {
            return a[0] - a[1] < b[0] - b[1];
        });

        int n = costs.size() / 2;
        int res = 0;
        for (int i = 0; i < n; i++) res += costs[i][0];
        for (int i = n; i < n * 2; i++) res += costs[i][1];
        return res;
    }
};

int main() {

    vector<vector<int>> costs = {
            {10, 20},
            {30, 200},
            {400, 50},
            {30, 20},
    };
    cout << Solution().twoCitySchedCost(costs) << endl;  // 110

    return 0;
}
